浅谈树状数组

一、啥是树状数组？

树状数组，是支持 $O(logn)$ 单点修改，$O(logn)$ 前缀和查询的数据结构。

先来看代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
LL tre[N]; int n, m;
int lowbit(int x) {
    return x & (-x);
}
void add(int pos, LL val) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        tre[i] += val;
    }
}
LL query(int pos) {
    LL ret = 0;
    for (int i = pos; i; i &= (i - 1)) {
        ret += tre[i];
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), add(i, x);
    for (int op, x, k; m--; ) {
        scanf("%d%d%d", &op, &x, &k);
        if (op == 1) add(x, (LL)k);
        else printf("%lld\n", query(k) - query(x - 1));
    }
    return 0;
}

二、树状数组的tre[i]含义是什么

举例：

所以，$tre_i$ 表示从第 $i$ 位开始往前数 $\operatorname{lowbit}(x)$ 个数的和。

那么如果要求第 $1 \sim 77$ 的数的和，就需要 $tre[(1001101)_2] + tre[(1001100)_2] + tre[(1001000)_2] + tre[(1000000)_2]$

用几张图来感性认知一下树状数组：

假如要更新 $A_{21}$ ，则需要更新 $tre[21], tre[22], tre[24], tre[32]$ 。

既然理解了，那就写代码吧！